package com.zrkizzy.doublepointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 18. 四数之和
 *
 * @author zhangrongkang
 * @since 2022/11/28
 * @see <a href="https://leetcode.cn/problems/4sum/description/">https://leetcode.cn/problems/4sum/description/</a>
 */
public class 四数之和 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 定义返回结果集
        List<List<Integer>> result = new ArrayList<>();
        // 定义双指针
        int left = 0, right = 0;
        // 将数组进行排序
        Arrays.sort(nums);

        // 遍历
        for (int k = 0; k < nums.length; k++) {
            // 对 nums[k] 进行剪枝操作
            if (nums[k] > 0 && nums[k] > target) {
                return result;
            }
            // 对 nums[k] 进行去重操作
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }

            // 遍历左右指针
            for (int i = k + 1; i < nums.length; i++) {
                // 对 nums[k] 和 nums[i] 进行去重操作
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }

                // 赋值左右指针
                left = i + 1;
                right = nums.length - 1;

                // 循环遍历左右指针
                while (right > left) {
                    // 计算四数之和
                    long sum = (long)nums[k] + nums[i] + nums[left] + nums[right];
                    // 判断四数之和
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        // 对 nums[right] 进行去重操作
                        while (right > left && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        // 对 nums[left] 进行去重操作
                        while (right > left && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        // 移动双指针
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}
